;; This time, target is a polynomial
(defparameter *target* #(1.0 -1.5 1.24 -3.6 -4.2 1.8 -2.7 5.6))
(defparameter *mutation-rate* 0.05)
(defparameter *mutation-step-size* 0.1
  "How much difference one mutation can make")

(defun fitness (x)
 (loop for index below (length x)
       sum (if (eql (elt x index)
                    (elt *target* index))
               1
               0)))

(defun mutate (x &optional (mutation-rate *mutation-rate*))
 "Destructively introduce random letters or spaces into x"
 (dotimes (index (length x))
   (if (probability mutation-rate)
       (setf (elt x index) (random-letter))))
 x)

(defun probability (p)
 "Return true with a probability p"
 (<= 0
     (random 1.0)
     p))

(defun random-letter ()
 (let ((choices "   abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzaeiouaeiouaeiouaeiouaeioueeeeee"))
   (elt choices (random (length choices)))))

(defparameter *gene-pool-size* 20)
(defparameter *gene-pool* (make-array *gene-pool-size*
                                     :element-type 'simple-base-string
                                     :initial-element ""
                                     :fill-pointer nil
                                     :adjustable nil))

(defun fill-gene-pool (&optional (candidate
                                 (make-string (length *target*)
                                              :initial-element #\ )))
 "Fill the gene pool with mutated versions of a given string, which
  defaults to all spaces"
 (dotimes (index (length *gene-pool*))
   (setf (elt *gene-pool* index)
         (mutate (copy-seq candidate)))))

(defun best-of-gene-pool ()
 "Return the best candidate in the gene pool"
 (let ((best (elt *gene-pool* 0)))
   (loop for candidate across *gene-pool*
         do (when (> (fitness candidate)
                     (fitness best))
              (setf best candidate)))
   best))

(defun evolve (generations)
 (dotimes (current-generation generations)
   (fill-gene-pool (best-of-gene-pool))))